package hah;

import org.omg.CORBA.MARSHAL;
import sun.nio.cs.ext.MacThai;

import java.text.DecimalFormat;
import java.util.*;

public class leetcode {
    public int countSegments(String s) {
        char[] arr=s.toCharArray();
        if (arr.length==0){
            return 0;
        }
        int count=0;
        int flag=1;
        for (char c:arr){
            if (c!=' '&&flag==1){
                count++;
                flag=0;
            }else if (c==' '){
                flag=1;
            }
        }
        return count;
    }

    public int arrangeCoins(int n) {
        int i=1;
        while (n>=i){
            n-=i;
            i++;
        }
        return i-1;
    }

    public int[] plusOne(int[] digits){
        int len= digits.length;
        for (int i=len-1;i>=0;i--){
            if (digits[i]==9){
                digits[i]=0;
            }else {
                digits[i]++;
                return digits;
            }
        }
        digits=new int[len+1];
        digits[0]=1;
        return digits;
    }
    public int[] constructRectangle(int area) {
            int[] res=new int[2];
            int a=(int)Math.floor(Math.sqrt(area));
            int b=(int)Math.ceil(Math.sqrt(area));
            while (a*b!=area){
                if (a*b>area)
                    a--;
                else
                    b++;
            }
            res[0]=b;
            res[1]=a;
            return res;
    }

    private char[] temp;
    private int len;
    public boolean reorderedPowerOf2(int n) {
        String s=n+"";
        char[] arr=s.toCharArray();
        temp=arr;
        Arrays.sort(temp);
        len=arr.length;
        return fun(0);
    }
    public boolean fun(int n){
        if (n>len-1){
                String s = new String(temp);
                System.out.println(s);
                int t = Integer.parseInt(s);
                System.out.println(t + " ....");
                boolean b = dividedby2(t);
                if (b == true) {
                    return true;
                }
        }else {
            for (int i=n;i<len;i++){
                char c=temp[n];
                temp[n]=temp[i];
                temp[i]=c;
                if (temp[0]=='0')
                    continue;
                boolean b=fun(n+1);
                if (b==true)
                    return true;
                c=temp[i];
                temp[i]=temp[n];
                temp[n]=c;
            }
        }
        return false;
    }
    public boolean dividedby2(int n){
        if (n==1)
            return true;
        double n2=n;
        while (n2!=1){
            n2/=2;
            if (n2<1){
                return false;
            }
        }
        return true;
    }
    public String longestPalindrome(String s) {
        char[] chars=s.toCharArray();
        int len= chars.length;
        boolean[][] b=new boolean[len][len];
        for (int n=0;n<len;n++){
            for (int i=0;i<len-n;i++){
                int j=i+n;
                if (i==j)
                    b[i][j]=true;
                else if (i+1==j)
                    b[i][j]=(chars[i]==chars[j]);
                else
                    b[i][j]=(b[i+1][j-1])&&(chars[i]==chars[j]);

            }
        }
        for (int n=len-1;n>=0;n--){
            for (int i=0;i<len-n;i++){
                int j=i+n;
                if (b[i][j]==true){
                    return s.substring(i,j+1);
                }
            }
        }
        return "";
    }

    public void show(boolean[][] b){
        for (int i=0;i<b.length;i++){
            for (int j=0;j<b.length;j++){
                System.out.print(b[i][j]+" ");
            }
            System.out.println();
        }
    }
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        trace(nums,0,lists);
        return lists;
    }
    public void trace(int[] nums,int t,List<List<Integer>> lists){
            if (t==nums.length) {
                ArrayList<Integer> list=new ArrayList<>();
                for (int i:nums){
                    list.add(i);
                }
                lists.add(list);
            }
            else{
                for (int i=t;i< nums.length;i++){
                    int temp=nums[t];
                    nums[t]=nums[i];
                    nums[i]=temp;
                    trace(nums,t+1,lists);
                    temp=nums[i];
                    nums[i]=nums[t];
                    nums[t]=temp;
                }
            }

    }
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        int[] temp=new int[nums.length];
        trace2(nums,temp,0,lists);
        return lists;
    }
    public void trace2(int[] nums,int[] temp,int t,List<List<Integer>> lists){
        if (nums.length==t){
            ArrayList<Integer> list=new ArrayList<>();
            for (int i=0;i< nums.length;i++){
                if (temp[i]!=0)
                    list.add(nums[i]);
            }
            lists.add(list);
        }else {
            for (int i=0;i<=1;i++){
                temp[t]=i;
                trace2(nums,temp,t+1,lists);
            }
        }
    }
    public int reverse(int x) {
        int ans=0;
        while (x!=0){
            int temp=x%10;
            x=x/10;
            if (ans>Integer.MAX_VALUE/10||(ans==Integer.MAX_VALUE/10&&temp>Integer.MAX_VALUE%10)){
                return 0;
            }
            if (ans<Integer.MIN_VALUE/10||(ans==Integer.MIN_VALUE/10&&temp<Integer.MIN_VALUE%10)){
                return 0;
            }
            ans=ans*10+temp;
        }
        return ans;
    }
    public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int distance=Integer.MAX_VALUE;
            for (int i=0;i< nums.length;i++){
                int temp_target=target- nums[i];
                int j=0;
                int k= nums.length-1;
                while (j!=k&&j< nums.length&&k>-1){
                    if (j==i)
                        j++;
                    if (k==i)
                        k--;
                    if (j==k)
                        break;
                    if (nums[j]+ nums[k]<target-nums[i]){
                        if (Math.abs(distance)>target-nums[i]-nums[j]-nums[k])
                            distance=target-nums[i]-nums[j]-nums[k];
                        j++;
                    }else {
                        if (Math.abs(distance)>nums[i]+nums[j]+nums[k]-target)
                            distance=target-nums[i]-nums[j]-nums[k];
                        k--;
                    }
                }
            }
            return target-distance;
    }

    public boolean canJump(int[] nums) {
        int maxIndex=0;
        for(int i=0;i<=nums.length;i++){
            for (int j=0;j<=maxIndex;j++){
                if (j+nums[j]>maxIndex)
                    maxIndex=j+nums[j];
            }
        }
        return maxIndex>=nums.length-1;
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int[] balance=new int[gas.length];
        int min= Integer.MAX_VALUE;
        int minIndex=0;
        int total=0;
        for (int i=0;i<gas.length;i++){
            balance[i]=gas[i]-cost[i];
        }
        for (int i=0;i< balance.length;i++){
            total+=balance[i];
            if (total<min){
                minIndex=i;
                min=total;
            }
        }
        return total<0?-1:(minIndex+1)% balance.length;
    }

    private HashSet<Integer> set=new HashSet<>();
    public int distributeCandies(int[] candyType) {
        int len=candyType.length;
        int type=0;
        for (int i=0;i<len;i++){
            if (!set.contains(candyType[i])){
                set.add(candyType[i]);
                type++;
            }
        }
        return type>=len/2?len/2:type;
    }

    public int trap(int[] height) {
        int sum=0;
        for (int i:height)
            sum += i;
        int left=0;
        int right= height.length-1;
        int h=1;
        int total=0;
        while (left<=right){
            while (height[left]<h&&left<=right)
                left++;
            while (height[right]<h&&left<=right)
                right--;
            total+=right-left+1;
            h++;
        }
        return total-sum;

    }

    public boolean isPerfectSquare(int num) {
        int res=0;
        int left=0; int right=num;
        while (left<=right){
            int mid=(left+right)/2;
            res=mid*mid;
            if (res==num)
                return true;
            else if (res>num)
                right=mid-1;
            else
                left=mid+1;
        }
        return false;
    }

    public int longestSubsequence2(int[] arr, int difference) {
        //做错了呜呜呜呜呜 以后要认真读题再做啊！！ letcode1218
        int len=arr.length;
        boolean[][] dis=new boolean[len][len];
        for (int k=0;k<len;k++){
            for (int i=0;i+k<len;i++){
                int j=i+k;
                if (i==j)
                    dis[i][j]=true;
                else if (i+1==j)
                    dis[i][j]=(arr[i]+difference==arr[j]);
                else
                    dis[i][j]=((dis[i+1][j-1]==true)&&(arr[i+1]-arr[i]==difference)&&(arr[j]-arr[j-1]==difference));
            }
        }
        for (int i=0;i<len;i++){
            for (int j=0;j<len;j++){
                System.out.print(dis[i][j]+" ");
            }
            System.out.println();
        }
        for (int k=len-1;k>-1;k--){
            for(int i=0;i+k<len;i++){
                int j=i+k;
                if (dis[i][j]==true)
                    return k+1;
            }
        }
        return arr[0];
    }

    public int longestSubsequence(int[] arr, int difference) {
        HashMap<Integer,Integer> map=new HashMap<>();
        int ans=1;
        int len=arr.length;
        int index=0;
        while (index<len){
            int val=map.getOrDefault(arr[index],0);
            map.put(arr[index],++val);
            ans=Math.max(ans,val);
        }
        return ans;
    }

    public int missingNumber(int[] nums) {
        /*HashSet<Integer> map=new HashSet<>();
        for (int i=0;i<=nums.length;i++)
            map.add(i);
        for (int i:nums){
            if (map.contains(i))
                map.remove(i);
        }
        return map.iterator().next();*/
        int ans=0;
        for (int i:nums)
            ans^=i;
        for (int i=0;i<=nums.length;i++)
            ans^=i;
        return ans;
    }

    public static void main(String[] args) {
        leetcode w=new leetcode();



    }
}
